public class Sort {
    //直接插入排序 
    //最好情况下: O(N)
    //最坏情况下：O(N^2)
    public void insertSort(int[] arr) {
        int size = arr.length;
        for (int i = 1; i < size; i++) {
            int j = i - 1;
            int tmp = arr[i];
            for(; j >= 0; j--) {
                if(arr[j] > tmp) {
                    arr[j+1] = arr[j];
                } else {
                    arr[j+1] = tmp;
                    break;
                }
            }
            arr[j+1] = tmp;
        }
    }

    //希尔排序 O(N^1.3 ~ N^1.5) 时间复杂度和增量与待排序的数据有关
    public void shellSort(int[] arr) {
        int size = arr.length;
        int gap = size / 2;
        while(gap > 0) {
            for (int i = gap; i < size; i++) {
                int j = i - gap;
                int tmp = arr[i];
                for(; j >= 0; j-=gap) {
                    if(arr[j] > tmp) {
                        arr[j+gap] = arr[j];
                    } else {
                        arr[j+gap] = tmp;
                        break;
                    }
                }
                arr[j+gap] = tmp;
            }
            gap /= 2;
        }
    }

    //快速排序
    public void quickSort(int[] arr) {
        quick(arr, 0, arr.length - 1);
    }

    private void quick(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }
        int pivot = partition(arr,left,right);

        quick(arr,0,pivot-1);
        quick(arr, pivot+1, right);
    }

    private int partition(int[] arr, int left, int right) {
        int key = arr[left];
        int tmpL = left;
        left++;
        while(left < right) {
            while(left < right && arr[right] >= key) {
                right--;
            }
            while(left < right && arr[left] <= key) {
                left++;
            }
            swap(arr, left, right);
        }
        swap(arr,left,tmpL);
        return left;
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    //堆排序
    public void heapSort(int[] arr) {
        int size = arr.length;
        //创建大根堆
        for (int parent = (arr.length - 1 - 1) / 2; parent >= 0; parent--) {
            shirtUp(arr, parent, size);
        }

        //升序排序
        for (int i = size - 1; i > 0; i--) {
            swap(arr,0,i);
            shirtDown(arr,0,size);
        }
    }

    private void shirtDown(int[] arr, int parent, int size) {
        int child = parent * 2 + 1;
        if(child + 1 < size && arr[child+1] > arr[child]) {
            child++;
        }

        while(parent < size) {
            if(arr[parent] < arr[child]) {
                swap(arr,parent,child);
                //继续向下调整
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }

    private void shirtUp(int[] arr, int parent, int size ) {
        int child = 2 * parent + 1; //左孩子

        if(child + 1 < size && arr[child+1] > arr[child]) {
            child++;
        }

        while(parent >= 0) {
            if(arr[parent] < arr[child]) {
                swap(arr,parent,child);
                //继续向上调整
                child = parent;
                parent = child * 2 + 1;
            } else {
                break;
            }
        }
    }

    //选择排序
    public void selectSort(int[] arr) {
        int size = arr.length;
        for (int i = 0; i < size - 1; i++) {
            int minIndex = i;
            for (int j = i+1; j < size; j++) {
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr,minIndex,i);
        }
    }

    //归并排序
    public void mergerSort(int[] arr) {
        merger(arr,0 ,arr.length - 1);
    }

    private void merger(int[] arr, int left, int right) {
        int mid = (left + right) / 2;

        //分解
        merger(arr,0,mid);
        merger(arr,mid+1,right);

        //合并
        merger_sort(arr,left,mid,right);
    }

    private void merger_sort(int[] arr, int start, int mid, int end) {
        int[] tmp = new int[end - start + 1];
        int s1 = start;
        int s2 = mid + 1;
        int e1 = mid;
        int e2 = end;

        int k = 0;
        while(s1 <= e1 && s2 <= e2) {
            if(arr[s1] < arr[s2]) {
                arr[k++] = arr[s1++];
            } else {
                arr[k++] = arr[s2++];
            }
        }

        while(s1 <= e1) {
            tmp[k++] = arr[s1++];
        }

        while(s2 <= e2) {
            tmp[k++] = arr[s2++];
        }

        //放回原数组
        k= 0;
        for (int i = start; i <= end; i++) {
            arr[i] = tmp[k];
            k++;
        }
    }

    public void bubbleSort(int[] arr) {
        int len = arr.length;
        boolean flag = true;
        for (int i = 0; flag && i < len - 1; i++) {
            flag = false;
            for (int j = 0; j < len - i - 1; j++) {
                if(arr[j] > arr[j + 1]) {
                    swap(arr,j,j+1);
                    flag = true;
                }
            }
        }
    }
}
